/*
 * @lc app=leetcode.cn id=122 lang=cpp
 *
 * [122] 买卖股票的最佳时机 II
 */
#include "include.h"
// @lc code=start
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n < 2){return 0;}
        // let try greedy
        int res = 0;
        int date = 0;
        while (date < n-1){
            if (prices[date]>=prices[date+1]){date++;}
            // start to increace now
            int sellDate = date;
            while (sellDate < n-1){
                if (prices[sellDate]<=prices[sellDate+1]){sellDate++;}
                else break;
            }
            // a deal done, start from that time
            res += prices[sellDate] - prices[date];
            date = sellDate;
        }
        return res;
        
        // use DP
        // dp[i][j] (i<j) : best profit from day i to day j
        /*
        dp[0][4] = max(dp[0][1] + dp[1][4],
                       dp[0][2] + dp[2][4],
                       dp[0][3] + dp[3][4])
        */ 
        int dp[n][n];
        memset(dp, 0, n*n*sizeof(int));
        for (int i=0;i<n-1;i++){
            dp[i][i+1] = std::max(prices[i+1] - prices[i], 0);
        }
        for (int step=2;step<n;step++){
            for (int start=0;start<n-step;start++){
                // all slit of day (start~start+step)
                int posibleProfit = 0;
                for (int i=1;i<step;i++){
                    int tempProfit = dp[start][start+i]
                            + dp[start+i][start+step];
                    if (tempProfit>posibleProfit){
                        posibleProfit = tempProfit;
                    }

                    // log
                    // if (start==0 and step==2){
                    //     printf("dp[%d][%d]=dp[%d][%d]+dp[%d][%d]=%d+%d=%d\n"
                    //     ,
                    //     start,start+step,
                    //     start, start+i,
                    //     start+i,start+step,
                    //     dp[start][start+i], dp[start+i][start+step],
                    //     tempProfit
                    //     );
                    // }

                }
                dp[start][start+step] = posibleProfit;
            }
        }

        // log
        // printf("log\n");
        // for (int i=0;i<n;i++){
        //     for (int j=0;j<n;j++){
        //         printf("%d ", dp[i][j]);
        //     }
        //     printf("\n");
        // }

        return dp[0][n-1];
    }
};

        // maybe just like dfs / back trace
        // eg : prices = [7,1,5,3,6] 
        /*
        \  7  1  5  3  6
        7  0 -6 -2 -4 -1
        1     0  4  2  5
        5        0 -2  1
        3           0  3
        6              0
        */
        // operations :
        // pass <=> sell and buy <=> go along diag 0
        // buy&sell <=> go right n and then down n to diag 0

// @lc code=end

